﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_39_CombinationSum
{
    class MainPoject
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(CombinationSum(new int[] { 2, 3, 6, 7 }, 5));
            foreach (var item1 in CombinationSum(new int[] { 2, 7, 6, 3, 5, 1 }, 9))
            {
                foreach (var item in item1)
                {
                    Console.Write(item + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }
        public static IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            //思路：递归+回溯（可以）
            //双指针（不行）
            //队列(思考不周)

            #region 递归
            //DFS or  BFS  树
            IList<IList<int>> list = new List<IList<int>>();
            int sum = 0;
            int index = 0;

            for (int i = 0; i < candidates.Length; i++)
            {
                Tree(list, new List<int>(), sum, candidates, target, candidates[i]);
            }
            return list;
            #endregion

            #region 队列
            //Array.Sort(candidates);
            //IList<IList<int>> list = new List<IList<int>>();
            //Queue<int> que = new Queue<int>();

            //for (int i = 1; i <= candidates.Length ; i++)
            //{
            //    int delta = i;
            //    int index = 0;
            //    int sum = 0;
            //    que.Clear();
            //    while (index < candidates.Length)
            //    {
            //        if (sum == target)
            //        {
            //            if (!IsRepeat(list,que)) list.Add(new List<int>(que));

            //            if (que.Count > 0)
            //            {
            //                if (IsCheck(que)) index += delta;
            //                int num = que.Dequeue();
            //                sum -= num;
            //            }
            //            else
            //            {
            //                Console.WriteLine("Error1");
            //            }
            //        }
            //        else if (sum > target)
            //        {
            //            if (IsCheck(que)) index += delta;
            //            int num = que.Dequeue();
            //            sum -= num;
            //        }
            //        else
            //        {
            //            que.Enqueue(candidates[index]);
            //            sum += candidates[index];
            //        }
            //    }
            //}

            //return list;
            #endregion
        }

        public static void Tree(IList<IList<int>> lists, List<int> list, int sum, int[] candidates, int target, int value)
        {
            sum += value;
            list.Add(value);

            if (sum == target)
            {

                list.Sort();
                if (!IsRepeat(lists, list))
                {
                    lists.Add(list);
                }
            }
            else if (sum > target)
            {
                return;
            }
            else
            {
                for (int i = 0; i < candidates.Length; i++)
                {
                    List<int> s = new List<int>();
                    s.AddRange(list);
                    Tree(lists, s, sum, candidates, target, candidates[i]);
                }
            }
        }


        /// <summary>
        /// 去重
        /// </summary>
        /// <param name="list"></param>
        /// <param name="que"></param>
        /// <returns></returns>
        public static bool IsRepeat(IList<IList<int>> list, IList<int> que)
        {
            bool res = false;
            foreach (var item in list)
            {
                if (item.Count == que.Count)
                {
                    res = true;
                    for (int i = 0; i < item.Count; i++)
                    {
                        if (item[i] != que[i])
                        {
                            res = false;
                        }
                        //else
                        //{
                        //    res = true;
                        //}
                    }
                    if (res)
                    {
                        return res;
                    }
                }
            }
            return res;
        }

        public static bool IsCheck(Queue<int> que)
        {
            if (que.Count <= 0) return true;
            List<int> list = new List<int>(que);
            int val = list[0];
            bool res = true;
            for (int i = 0; i < list.Count; i++)
            {
                if (val != list[i])
                {
                    res = false;
                }
            }
            return res;
        }

    }
}
